import java.util.Scanner;

public class ReplaceableTree<Element extends Comparable> extends Tree<Element> {

	public ReplaceableTree(Element node) {
		super(node);
	}

	public ReplaceableTree() {
		super();
	}

	@Override
	public void add(Element newElement) {
		if (super.root == null) {
			super.root = new Node(newElement);
		} else {
			Node currentNode = this.searchnull();
			if (currentNode.getLeft() == null) {
				Node tempNode = new Node(newElement);
				currentNode.setLeft(tempNode);
				Node lastNode = this.goToLast();
				lastNode.setNext(tempNode);
				tempNode.setPrevious(lastNode);
			} else {
				Node tempNode = new Node(newElement);
				currentNode.setRight(tempNode);
				Node lastNode = this.goToLast();
				lastNode.setNext(tempNode);
				tempNode.setPrevious(lastNode);
			}
		}
	}

	private Node goToLast() {
		if (super.root != null) {
			Node tempNode = super.root;
			while (tempNode.getNext() != null) {
				tempNode = tempNode.getNext();
			}
			return tempNode;
		} else {
			return null;
		}
	}

	private Node searchnull() {
		if (super.root == null) {
			return null;
		}
		Queue queue = new Queue();
		queue.push(root);
		while (!queue.empty()) {
			Node node = queue.pop();
			if (node.getLeft() == null || node.getRight() == null) {
				return node;
			}
			if (queue.empty()) {
				queue.push(node.getRight());
				queue.push(node.getLeft());
			}
		}
		return null;
	}

	@Override
	public Iter<Boolean> search(Element element) {
//		String result = depthSearch(node, rootNode);
//        if (result == null) {
//			return "Knoten wurde nicht gefunden"; 
//		}
		return null;
	}

	@Override
	public TreeIter contains(Element element) {
		return null;
	}

//	public void replace(String position, String subTree) {
//		StringNode toAdd = rootNode;
//		Scanner s = new Scanner(position).useDelimiter(" ");
//		String temp;
//		while (s.hasNext()) {
//			temp = s.next();
//			if (temp.equals("left")) {
//				toAdd = toAdd.getLeftChild();
//			} else if (temp.equals("right")) {
//				toAdd = toAdd.getRightChild();
//			}
//			System.out.println(temp);
//		}
//		toAdd = this.createSubTree(subTree);
//		//missing
//	}
//	private StringNode createSubTree(String subTree) {
//		Scanner s = new Scanner(subTree).useDelimiter("\n");
//		String currentline = "";
//		if (s.hasNext()) {
//			currentline = s.next();
//		}
//		currentline = currentline.trim();
//		currentline = currentline.substring(4);
//
//		return null;
//	}
//	private String depthSearch(String wantedNode, SNode currentNode) {
//		if (currentNode == null) {
//			return null;
//		}
//		String curStr = currentNode.getLabel();
//		if (curStr.equals(wantedNode)) {
//			return "";
//		}
//		String resultleft = depthSearch(wantedNode, currentNode.getLeftChild());
//		String resultright = depthSearch(wantedNode, currentNode.getRightChild());
//		if (!(resultleft == null)) {
//			return "left " + resultleft;
//		}
//		if (!(resultright == null)) {
//			return "right " + resultright;
//		}
//		return null;
//	}
	private class QueueElement {

		private Node node;
		private QueueElement prev;

		public QueueElement(Node node, QueueElement prev) {
			this.node = node;
			this.prev = prev;
		}

		public Node getNode() {
			return this.node;
		}

		public QueueElement getPrev() {
			return prev;
		}

		public void setPrev(QueueElement prev) {
			this.prev = prev;
		}
	}

	private class Queue {

		private QueueElement ground = null;

		public void push(Node node) {
			if (ground == null) {
				this.ground = new QueueElement(node, null);
			} else {
				ground = new QueueElement(node, ground);
			}
		}

		public Node pop() {
			if (ground != null) {
				QueueElement tempqueueelement = ground;
				ground = ground.getPrev();
				return tempqueueelement.getNode();
			} else {
				return null;
			}
		}

		public boolean empty() {
			if (ground == null) {
				return true;
			} else {
				return false;
			}
		}
	}
}
